package com.shm.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 2006. 差的绝对值为 K 的数对数目
 * 给你一个整数数组 nums 和一个整数 k ，请你返回数对 (i, j) 的数目，满足 i < j 且 |nums[i] - nums[j]| == k 。
 *
 * |x| 的值定义为：
 *
 * 如果 x >= 0 ，那么值为 x 。
 * 如果 x < 0 ，那么值为 -x 。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,2,1], k = 1
 * 输出：4
 * 解释：差的绝对值为 1 的数对为：
 * - [1,2,2,1]
 * - [1,2,2,1]
 * - [1,2,2,1]
 * - [1,2,2,1]
 * 示例 2：
 *
 * 输入：nums = [1,3], k = 3
 * 输出：0
 * 解释：没有任何数对差的绝对值为 3 。
 * 示例 3：
 *
 * 输入：nums = [3,2,1,5,4], k = 2
 * 输出：3
 * 解释：差的绝对值为 2 的数对为：
 * - [3,2,1,5,4]
 * - [3,2,1,5,4]
 * - [3,2,1,5,4]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 200
 * 1 <= nums[i] <= 100
 * 1 <= k <= 99
 * @author SHM
 */
public class CountKDifference {

    public int countKDifference(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        for(int i=0;i<n-1;i++){
            for(int j=i+1;j<n;j++){
                if(Math.abs(nums[i]-nums[j])==k){
                    ans++;
                }
            }
        }
        return ans;
    }

    /**
     * 方法二：哈希表 + 一次遍历
     * 思路
     *
     * 我们进行一次遍历，遍历时下标代表 jj。对每一个 jj，我们需要知道在这个 jj 之前的符合条件的 ii 的个数，即满足 |\texttt{nums}[i] - \texttt{nums}[j]| = k∣nums[i]−nums[j]∣=k 的 ii 的个数，亦即满足 \texttt{nums}[i] = \texttt{nums}[j] + knums[i]=nums[j]+k 或 \texttt{nums}[i] = \texttt{nums}[j] - knums[i]=nums[j]−k 的 ii 的个数。使用哈希表可以在 O(1)O(1) 的时间内统计出这样的个数，因此在遍历时我们可以使用一个哈希表来维护不同数值的频率，并统计符合条件的数对总数。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 为数组 \textit{nums}nums 的长度。我们仅使用了一次遍历来寻找所有符合条件的数对。
     *
     * 空间复杂度：O(n)O(n)。哈希表消耗了 O(n)O(n) 的空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/count-number-of-pairs-with-absolute-difference-k/solution/chai-de-jue-dui-zhi-wei-k-de-shu-dui-shu-xspo/
     * @param nums
     * @param k
     * @return
     */
        public int countKDifference_1(int[] nums, int k) {
            int res = 0, n = nums.length;
            Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            for (int j = 0; j < n; ++j) {
                res += cnt.getOrDefault(nums[j] - k, 0) + cnt.getOrDefault(nums[j] + k, 0);
                cnt.put(nums[j], cnt.getOrDefault(nums[j], 0) + 1);
            }
            return res;
        }
}
